WSEAS Transactions on Circuits and Systems


Print ISSN: 1109-2734
E-ISSN: 2224-266X

Volume 17, 2018

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

Volume 16, 2017


Protein Folding in 3D Lattice HP Model Using Heuristic Algorithm

AUTHORS: Metodi Traykov, Nicola Yanev, Radoslav Mavrevski, Borislav Yurukov

Download as PDF

ABSTRACT: The proteins play a key role in many vital functions in living organisms. The tertiary structure of the proteins determines their functions. Predicting of a protein's tertiary structure can be the base for development of treatments for diseases such as Alzheimer's disease and cystic fibrosis. Therefore, the predicting of a protein's tertiary structure from its amino acid sequence from long time is one of the fundamental problems in computational biology, molecular biology, biochemistry, and physics. The prediction of a protein’s tertiary structure from its amino acid sequence is known as Protein Folding Problem. This is the NP-complete problem. In this article we propose extension of the heuristic algorithm that solves the problem in 2D (described by some of authors on this article) to solve the protein folding problem in 3D lattice HP model.

KEYWORDS: NP-complete problem, protein folding problem, HP folding, HP model, 3D lattice, integer programming, bioinformatics, heuristics.

REFERENCES:

[1] K. Dill, Theory for the folding and stability of lobular proteins, Biochemistry-US, Vol. 24, 1985, pp. 1501-1509.

[2] K. Dill, K. Lau, A Lattice Statistical Mechanics Model of the Conformational Sequence Spaces of Proteins, Macromolecules, Vol. 22, 1989, pp. 3986-3997.

[3] C. Lin, M. Hsieh, An efficient hybrid Taguchigenetic algorithm for protein folding simulation, Expert Systems with Applications, Vol. 36, 2009, pp. 12446-12453.

[4] J. Blazewick, K. Dill, P. Lukasiak, et al., A Tabu Search Strategy For Finding Low Energy Structures Of Proteins In Hp-Model, CMST, Vol. 10, 2004, pp. 7-19.

[5] B. Berger, T. Leighton, Protein folding in the Hydrophobic-Hydrophilic (HP) is NPcomplete, J. Comput. Biol. Vol. 5, 1998, pp. 27-40.

[6] S. Istrail, A. Hurd, R. Lippert, et al., Prediction of self-assembly of energetic tiles and dominoes: Experiments, mathematics, and software, Technical Report SAND2002, 2000, Sandia National Laboratories.

[7] S. Istrail, F. Lam, Combinatorial algorithms for protein folding in lattice models: A survey of mathematical results, Commun. Inf. Syst., Vol. 9, 2009, pp. 303-346.

[8] M. Chen, W. Huang, A branch and bound algorithm for the protein folding problem in the HP Lattice Model, Genomics Proteomics Bioinformatics, Vol. 3, 2005, pp. 225-230.

[9] L. Toma, S. Toma, Contact interactions method: A new algorithm for protein folding simulations, Protein Sci., Vol. 5, 1996, pp. 147- 153.

[10] C. Lin, M. Hsieh, An efficient hybrid Taguchigenetic algorithm for protein folding simulation, Expert Systems with Applications, Vol. 36, 2009, pp. 12446-12453.

[11] Y. Zhang, J. Skolnick, Tertiary structure predictions on a comprehensive benchmark of medium to large size proteins, Biophys J., Vol. 87, 2004, pp. 2647-2655.

[12] N. Krasnogor, D. Pelta, P. Lopez, et al., Genetic Algorithms for the Protein Folding Problem: A Critical View, Proc. Engineering of intelligent systems, 1998, pp. 353-360.

[13] F. Liang, W. Wong, Evolutionary Monte Carlo for Protein Folding Simulations, J. Chem. Phys., Vol. 115, 2001, pp. 444-451.

[14] A. Shmygelska, H. Hoos, An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem, BMC Bioinformatics, Vol. 6, 2005, Article No.30.

[15] N. Yanev, M. Traykov, P. Milanov, B. Yurukov, Protein folding prediction in a cubic lattice in hydrophobic-polar model, J Comput. Biol., Vol. 24, 2017, pp. 412-421.

[16] N. Yanev, P. Milanov, I. Mirchev, Integer programming approaches to HP folding, Serdica J. Computing, Vol. 5, 2011, pp. 359- 366.

[17] M. Traykov, S. Angelov, N. Yanev, A New Heuristic Algorithm for Protein Folding in the HP Model, J Comput. Biol., Vol. 23, 2016, pp. 662-668.

[18] T. Jiang, Q. Cui, G. Shi, et al., Protein folding simulations for the hydrophobic-hydrophilic model by combining tabu search with genetic algorithms, J Chem. Phys. Vol. 119, 2003, pp. 4592-4596.

[19] M. Garza-Fabre, G. Toscano-Pulido, E. Rodriguez-Tello, Benchmark Sequences for the HP Model of Protein Structure Prediction: 2D square and 3D cubic lattices, 2003.

[20] N. Thilagavathi, T. Amudha, Acometaheuristic for 3D-hp protein folding optimization, ARPN Journal of Engineering and Applied Sciences, Vol. 10, 2015, pp. 4948- 4953.

[21] C. Lin, S. Su, Protein 3D HP Model Folding Simulation Using a Hybrid of Genetic Algorithm and Particle Swarm Optimization, Int. J. Fuzzy Syst, Vol. 13, 2011, pp. 140-147.

[22] C. Cotta, Protein structure prediction using evolutionary algorithms hybridized with backtracking, Artificial Neural Nets Problem Solving Methods, Vol. 2687, 2003, pp. 321- 328.

[23] M. Khimasia, P. Coveney, Protein structure prediction as a hard optimization problem: the genetic algorithm approach, Molecular Simulation, Vol. 19, 1997, pp.205-226.

WSEAS Transactions on Circuits and Systems, ISSN / E-ISSN: 1109-2734 / 2224-266X, Volume 17, 2018, Art. #12, pp. 89-98


Copyright © 2018 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board

Currently:

The editorial board is accepting papers.


WSEAS Main Site